看题解里有人说这题实在太水

但我连第一步对点分类都不会（虽然分类完后的确不会很难）

我依旧是太菜

好了进入正题

线段树上打 $\text{tag}$，因为它一直复制来复制去，不可能在没棵线段树上都进行修改，就考虑点的共同性质，相同性质的点可以一起修改，那么此时相当于只进行一次 $\text{modify}$ 就行了

可以将点分成五类：

  • 一类点：半覆盖（就是修改时会经过但是不打标记）
  • 二类点：全覆盖，打标记（区间被修改区间完全覆盖，会被访问到，被打标记）
  • 三类点：全覆盖，不打标记（区间被修改区间完全覆盖，但不会被访问到，就是打标记全覆盖节点的子节点，不被打标记）
  • 四类点：访问不到，会被下传标记
  • 五类点：访问不到，不会被下传标记

那么此时方案数转概率，令 $f_u$ 表示节点 $u$ 有被打标记的概率，即 $u$ 有被打标记的线段树占比，那么最终被打标记的节点 $u$ 个数即为 $f_u \times 2^n$（其中 $n$ 表示被修改次数）

但是会发现写四类点的时候还需要知道它祖先有没有被打标记，所以还需要设一个 $g_u$ 表示节点 $u$ 及其祖先被打标记的概率，开始转移

对一类点，复制后一半保持原样，一半必定无标记（因为是经过点肯定会被下传），其祖先同理
$$
f_u = \frac12(f_u + 0), g_u = \frac12(g_u + 0)
$$
对二类点，复制后一半保持原样，一半必定会被打标记
$$
f_u = \frac12(f_u + 1), g_u = \frac12(g_u + 1)
$$
对三类点，复制后一半保持原样，一半必定不会被下传标记，但其祖先必定会被标记
$$
f_u = f_u, g_u = \frac12(g_u + 1)
$$
对四类点，复制后一半保持原样，一半可能会被下传标记（必定会经过其父节点，否则它不可能成为四类点，同时是否会被下传标记取决于它祖先是否有标记，即 $g_u$）
$$
f_u = \frac12(f_u + g_u), g_u = g_u
$$
对五类点，复制后一半保持原样，一半也不会被影响
$$
f_u = f_u, g_u = g_u
$$
故五类点可不做处理

但是三类点的数目很多，是 $O (n)$ 级别，故对三类点的修改还需要打懒标记

再开一个 $sumf_u$ 维护其子树答案

最终答案即为 $sumf_1 \times 2^n$

时间复杂度 $O (m\log n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cstring>

#define lson root << 1
#define rson root << 1 | 1

#define MOD 998244353

using namespace std;

typedef long long LL;

const int MAXN = 8e05 + 10;

const LL inv2 = 499122177;

LL f[MAXN]= {0}, g[MAXN]= {0};
LL sumf[MAXN]= {0}, lazy[MAXN]= {0};
void build (int root, int left, int right) {
	lazy[root] = 1;
	if (left == right) return ;
	int mid = (left + right) >> 1;
	build (lson, left, mid);
	build (rson, mid + 1, right);
}
void maintain (int root) { sumf[root] = (f[root] + sumf[lson] + sumf[rson]) % MOD; }
void pushG (int root, LL value) {
	g[root] = (g[root] * value % MOD + 1ll - value + MOD) % MOD;
	lazy[root] = lazy[root] * value % MOD;
}
void pushF (int root) { f[root] = (f[root] + g[root]) % MOD * inv2 % MOD; maintain (root); }
void pushdown (int root) {
	if (lazy[root] == 1) return ;
	pushG (lson, lazy[root]); pushG (rson, lazy[root]);
	lazy[root] = 1;
}
void modify (int root, int left, int right, int L, int R) {
	if (L <= left && right <= R) {
		f[root] = (f[root] + 1) % MOD * inv2 % MOD; // 二类点
		g[root] = (g[root] + 1) % MOD * inv2 % MOD;
		pushG (lson, inv2); pushG (rson, inv2); // 三类点
		maintain (root);
		return ;
	}
	pushdown (root); // 三类点pushdown
	f[root] = f[root] * inv2 % MOD; // 一类点
	g[root] = g[root] * inv2 % MOD;
	int mid = (left + right) >> 1;
	if (L <= mid) modify (lson, left, mid, L, R);
	else pushF (lson); // 四类点
	if (R > mid) modify (rson, mid + 1, right, L, R);
	else pushF (rson); // 四类点
	maintain (root);
}

int N, M;

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}
inline void write (LL x) {
	if (x >= 10) write (x / 10);
	putchar (x % 10 + '0');
}

int main () {
	N = getnum (), M = getnum ();
	LL down = 1;
	build (1, 1, N);
	for (int q = 1; q <= M; q ++) {
		int type = getnum ();
		if (type == 2) { write (sumf[1] * down % MOD); puts (""); }
		else {
			down = down * 2ll % MOD;
			int l = getnum (), r = getnum ();
			modify (1, 1, N, l, r);
		}
	}

	return 0;
}

/*
5 5
2
1 1 3
2
1 3 5
2
*/